Bayankhongor được thành lập vào năm 1941 cùng với tHội đồng Công dân Bayankhongor. Tỉnh được hình thành từ 16 khu vực sum Bayankhongor và có khoảng 41 nghìn dân. Tỉnh ban đầu được đặt tên là Govi-Bumbugur, nhưng không lâu sau đó đã được đổi thành Bayankhongor.

Vào tháng 4 năm 1976, Bayankhongor đã nhận được giải thưởng Xô viết cho các sản phẩm chăn nuôi, thịt và len. Tỉnh đã nhận được sự trợ giúp từ Liên Xô cũ bao gồm các cơ sở hạ tầng và giáo dục. Tuy nhiên, Liên Xô cũng đã phá hủy một cách có hệ thống niềm tin tôn giáo cũng như các di sản trên địa bàn tỉnh, tiến hành thanh trừng tại các tu viện nổi tiếng như Tu viện Geegin và giết chết hàng nghìn sư sãi.

Zud, hay cơn bão lớn, xảy đến vào đầu năm 2000 đã tàn phá ngành chăn nuôi và nền kinh tế nói chung của Bayankhongor. Zud cũng bắt buộc tỉnh phải thay đổi về mặt xã hội khi ngày càng ít người sống bằng nghề chăn nuôi gia súc trong khi càng nhiều người chuyển đến tỉnh lị để tìm việc làm. Tổng dân số của tỉnh hiện nay là khoảng 80.000, ước tính trong số đó có 25-35.000 dân sống tại tỉnh lị.